package com.cuz.daileetcode;

import com.cuz.daileetcode.utils.ArrayUtils;

public class Day59 {


    public static class PreInGetPost {
        public static void main(String[] args) {
            int[] pre = {1, 2, 4, 5, 3, 7};
            int[] in = {4, 2, 5, 1, 7, 3};
            int[] post = solution1(pre, in);
            ArrayUtils.print(post);
        }

        /**
         * 根据先序中序得到后序
         *
         * @param pre 先序
         * @param in  中序
         * @return 后序遍历结果
         */
        public static int[] solution1(int[] pre, int[] in) {
            int len = pre.length;
            int[] post = new int[len];
            process(pre, 0, len - 1, in, 0, len - 1, post, 0, len - 1);
            return post;
        }

        /****
         * 递归的处理
         * 根据 pre[preStart....preEnd]的内容 和
         * in[inStart....inEnd]的内容填写
         * post[postStart....postEnd]的内容
         *
         * @param pre 前序遍历
         * @param preStart 前序遍历起始
         * @param preEnd 先序遍历结束位置
         * @param in 中序遍历结果
         * @param inStart 中序起始
         * @param inEnd 中序结束
         * @param post 后序
         * @param postStart 后序起始
         * @param postEnd 后序结束
         */
        private static void process(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd, int[] post, int postStart, int postEnd) {
            if (preStart > preEnd) {
                return;
            }
            //首先 后序最后一个位置的值 是前序第一个值
            post[postEnd] = pre[preStart];
            //在中序中找到当前数根节点的下标
            int curRootNodeIndex = indexOf(in, pre[preStart]);
            //左树规模
            int leftTreeSize = curRootNodeIndex - inStart;
            //右树规模
            int rightTreeSize = inEnd - curRootNodeIndex;

            //接下来 用 pre[preStart+1....preStart+leftTreeSize]
            // 和 in[inStart....curRootNodeIndex-1]的内容
            //搞定 post[postStart...postStart+leftTreeSize-1]的内容
            //即递归的处理左树
            process(pre, preStart + 1, preStart + leftTreeSize,
                    in, inStart, curRootNodeIndex - 1,
                    post, postStart, postStart + leftTreeSize - 1);

            //递归处理右树
            process(pre, preStart + 1 + leftTreeSize, preStart + 1 + leftTreeSize + rightTreeSize - 1,
                    in, curRootNodeIndex + 1, curRootNodeIndex + 1 + rightTreeSize - 1,
                    post, postEnd - rightTreeSize, postEnd - 1);
        }

        /****
         * 在数组arr中寻找target 返回index
         * @param arr 数组
         * @param target 目标值
         * @return 目标值下标
         */
        private static int indexOf(int[] arr, int target) {
            for (int index = 0; index < arr.length; index++) {
                if (arr[index] == target) {
                    return index;
                }
            }
            return -1;
        }

    }

    public static class Digital2Chinese {

        private static final String[] MEMORY = {"", "一", "二", "三", "四", "五", "六", "七", "八", "九"};

        private static String oneTo9(int num) {
            return MEMORY[num];
        }

        private static String oneTo99(int num) {
            if (num <= 9) {
                return oneTo9(num);
            }
            //10->一十，17 ->一十七
            int numOfTen = num / 10;
            String res = oneTo9(numOfTen);
            int rest = num % 10;
            return res + oneTo9(rest);
        }

//        private static String oneTo999(int num){
//            //Boring
//        }
    }
}
